package 剑指offer;

import java.util.Scanner;


/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:40:59 
* @Description：
* 
输入两个单调递增的链表，输出两个链表合成后的链表，
当然我们需要合成后的链表满足单调不减规则
*/

//类似于归并排序当中的merge
public class A16合并两个排序的链表 {

	
	//递归方法实现
	public static  ListNode Merge(ListNode list1,ListNode list2) {
		if (list1==null) {
			return list2;
		}
		if (list2==null) {
			return list1;
		}
		
		if (list1.val<=list2.val) {
			list1.next=Merge(list1.next, list2);
			return list1;
		}else {
			list2.next=Merge(list1, list2.next);
			return list2;
		}
	}

	
	//非递归
	
	/*
	 * 就是类似于归并排序当中的merge
	 * 1.先是类似于一个临时数组，在这里创建一个mergeHead用来保存合并的链表
	 * 2.当list1,list2都还没有遍历完之前，依次比较list1,val与list2.val
	 *    小的值的结点直接添加到mergeHead,并将指针由当前curren指向下一个current.next，
	 *     大的那个不动，继续与current.next重复比较
	 *    
	 *  3.不断重复上面的比较，直到两个当中的某一个链表遍历完了，这里不能保证两个链表都完了，只能保证其中一个是完了的
	 *  4.这时，只要判断到底是哪个链表完了，只需将未完的链表依次遍历完，按照mergeHead当前的顺序全部插入即可
	 */
	public ListNode Merge1(ListNode list1,ListNode list2) {
		if (list1==null) {
			return list2;
		}
		if (list2==null) {
			return list1;
		}
		
		ListNode mergeHead=null;
		ListNode current =null;
		while (list1!=null &&list2!=null) {
			if (list1.val<=list2.val) {
				if (mergeHead==null) {
					mergeHead=current=list1;
				}else {
					current.next=list1;
					current=current.next;
				}
				list1=list1.next;
			}else {
				if (mergeHead==null) {
					mergeHead=current=list2;
				}else {
					current.next=list2;
					current=current.next;
				}
				list2=list2.next;
			}
		}
		if (list1==null) {
			current.next=list2;
		}
		if (list2==null) {
			current.next=list1;
		}
		return mergeHead;
	}
	
	
	
    public static void main(String[] args) {
		
		Scanner scan=new Scanner(System.in);
        String[] array=scan.nextLine().split(" ");
        ListNode Head=new ListNode(Integer.parseInt(array[0]));
        ListNode nextNode=Head;
        for(int i=1;i<array.length;i++){
            ListNode newNode=new ListNode(Integer.parseInt(array[i]));
            nextNode.next=newNode;
            nextNode=newNode;
        }
        
        String[] array1=scan.nextLine().split(" ");
        ListNode Head1=new ListNode(Integer.parseInt(array1[0]));
        ListNode nextNode1=Head;
        for(int i=1;i<array1.length;i++){
            ListNode newNode=new ListNode(Integer.parseInt(array1[i]));
            nextNode.next=newNode;
            nextNode=newNode;
        }
        ListNode merge = Merge(Head, Head1);
        while (merge!=null) {
        	System.out.print(merge.val+" ");
        	merge=merge.next;
			
		}
	}
        
}
